package 题目集.贪心.不等式;

import java.util.Arrays;
import java.util.Scanner;

/**
 * https://www.acwing.com/problem/content/106/
 * 在一条数轴上有 N家商店，它们的坐标分别为 A1∼AN
 * 现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
 * 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
 *
 * 解法：
 *      仓库x到每个点的距离为：{|x-A1|+|x-A2|+...+|x-An|}
 *      仓库x到每个点的距离之和最小，即使得上式最小
 * 先说结论：n（商店数）为奇数，则取中位数；n为偶数，则取中位数两边的中间点
 * 证明：首先有基本绝对值不等式:|x-a|+|x-b|>=|a-b|。（可以画图证明，也可分类讨论证明这个不等式）
 *    令f(x)=|x-A1|+|x-A2|+...+|x-An|
 *    其中A1<=A2<=...<=An
 *    f(x)首尾组合，即f(x)=|x-A1|+|x-An|+|x-A2|+|x-An-1|+...>=|A1-An|+|A2-An-1|+...
 *    当n为奇数时
 *      当f(x)=|x-A1|+|x-An|+|x-A2|+|x-An-1|+...|x-Amid|>=|A1-An|+|A2-An-1|+...
 *      当x取到Amid位置时，使得不等式左右两边相等，即f(x)最小
 *    当n为偶数时：当x取到中间两数之间时，使得不等式左右两边相等，即f(x)最小
 *
 */
public class ch02_一维绝对值不等式_仓库选址 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int l = 0, r = n - 1;
        long res = 0;
        while (l < r) {
            res += a[r] - a[l];
            l++;
            r--;
        }
        System.out.println(res);
    }
}
